package oct2013;

public class MinimumWindowSubstring {
	public String minWindow(String S, String T) {
		int n = S.length();
		int[] need = new int[256];
		int tot = 0, ob = 0;
		for (int i = T.length() - 1; i >= 0; --i) {
			need[T.charAt(i)]++;
			tot++;
		}
		if (tot == 0)
			return "";
		int[] cnt = new int[256];
		int left = 0;
		String res = null;
		for (int i = 0; i < n; ++i) {
			int ch = S.charAt(i);
			if (need[ch] != 0) {
				if (cnt[ch] < need[ch])
					ob++;
				cnt[ch]++;
			}
			while (left <= i) {
				if (need[S.charAt(left)] == 0)
					left++;
				else if (cnt[S.charAt(left)] > need[S.charAt(left)]) {
					cnt[S.charAt(left)]--;
					left++;
				} else {
					break;
				}
			}
			if (ob == tot && (res == null || i - left + 1 < res.length())) {
				res = S.substring(left, i + 1);
			}
		}
		return res == null ? "" : res;
	}
}
